/* 
最小深度
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度 2.

来源: LeetCode第111题
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
// 递归实现
// 在实现的过程中，如果按照最大深度的方式来做会出现一个陷阱，即:
var minDepth = function (root) {
    // 递归终止条件 
    if (root === null) return 0;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};
// 当 root 节点有一个孩子为空的时候，此时返回的是 1， 但这是不对的，最小高度指的是根节点到最近叶子节点的最小路径，而不是到一个空节点的路径。

// 因此我们需要做如下的调整:
var minDepth = function (root) {
    if (root === null) return 0;
    // 左右孩子都不为空才能像刚才那样调用
    if (root.left && root.right)
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    // 右孩子为空了，直接忽略之
    else if (root.left)
        return minDepth(root.left) + 1;
    // 左孩子为空，忽略
    else if (root.right)
        return minDepth(root.right) + 1;
    // 两个孩子都为空，说明到达了叶子节点，返回 1
    else return 1;
};
// 这样程序便能正常工作了。

// 非递归实现
// 类似于最大高度问题，采用了层序遍历的方式，很容易理解。
var minDepth = function (root) {
    if (root === null) return 0;
    const queue = [root];
    let level = 0;
    while (queue.length) {
        // level ++ 后的值代表着现在已经处理完了几层节点
        level++;
        let size = queue.length;
        while (size--) {
            const parent = queue.shift();
            // 找到叶子节点
            if (!parent.left && !parent.right) return level;
            if (parent.left) queue.push(parent.left);
            if (parent.right) queue.push(parent.right);
        }

    }
    return level;
};